package leetcode.median;

import java.util.LinkedList;
import java.util.List;

/**
 * ClassName: $216_CombinationSum3
 * Description:
 * date: 2022-02-17 21:48
 *
 * @author liyifan
 */
public class $216_CombinationSum3 {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(n, 1, n, k);
        return res;
    }

    public void backtrack(int target, int start, int n, int k) {
        if (target == 0 && path.size() == k) {res.add(new LinkedList<>(path));}

        for (int i = start;i <= 9;i++) {
            if (target >= i) {
                path.add(i);
                backtrack(target - i, i + 1, n, k);
                path.remove(path.size() - 1);
            }
        }
    }

}
